<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>冒泡排序</title>
</head>
<body>
  <script>
    /** 冒泡排序
     * 
     * 工作原理：从数组的左面向右面遍历，依次比较相邻元素，如果 左元素 > 右元素，交换左右元素的位置。第一轮遍历完成后，数组最大的元素就被移动到数组最右端了。依次遍历
     * 
     * 设数组长度为 n
     * 1.对 [0, n-1] 数组进行冒泡，将数组最大元素移动到最后
     * 2.对 [0, n-2] 的元素进行冒泡，将第2大的元素移动到正确位置
     * 3.对 [0, n-3] 的元素进行冒泡，将第3大的元素移动到正确位置
     * 以此类推
     * 4.对 [0, 1] 的元素进行冒泡
     * 
     * 时间复杂度：O(n2)  空间复杂度：O(1)
    */

    const data = [4,3,5,2,6,1,7,9,8,0,10]
    function bubbleSort(arrs) {
      const arr = [...arrs]
      const length = arr.length
      // for (let i = 0; i < length; i++) {
      //   for (let j = 0; j < length - i; j++) {
      //     const tempj = arr[j];
      //     const tempj1 = arr[j+1];
      //     if(tempj > tempj1) {
      //       [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
      //     }
      //   }
      // }

      // 开启一个循环
      for (let i = length - 1; i >= 0; i--) {
        // 遍历 [0, i] 的元素。因为 [i, length-1] 的元素已经冒泡完成
        for (let j = 0; j < i; j++) {
          const tempj = arr[j];
          const tempj1 = arr[j+1];
          if(tempj > tempj1) {
            // 交换位置
            // arr[j] = tempj1
            // arr[j+1] = tempj
            [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
          }
        }
      }
      return arr
    }

    const result = bubbleSort(data)
    document.write('冒泡排序：', result)
  </script>
</body>
</html>